This invention pertains to the field of artificial intelligence, and more particularly, to an apparatus and method for a compositional decision support reasoning system for generating incremental and multiple conclusions.
This invention is related to the copending U.S. Application of Joseph Martinka, et. al. entitled xe2x80x9cAPPARATUS FOR A MULTI-MODAL ONTOLOGY ENGINExe2x80x9d, Ser. No. 09/470,848 filed on the same date as the present application, and hereby incorporates by reference all that is disclosed therein.
An organization""s most valuable asset is its knowledge. More and more companies are embracing knowledge-based system technology as a means of putting the right knowledge in the hands of the right people at the right time. Intelligent electronic manuals, internal help desks, customer support hotlines, call avoidance troubleshooting software, pre-sales assessment, configuration guides, and proactive system management are some of the ways that the emerging field of computer aided decision support allows people to perform critical tasks and make key decisions with the skill of the leading experts, but without the labor costs of employing experts in delivering the support services.
All of these computer-assisted solutions entail the employment of a decision support system, or a system that employs a knowledge representation paradigm to determine a solution to a problem. A knowledge representation paradigm comprises two components: a knowledge representation fact base and a reasoning system. A knowledge representation fact base is the means by which an expert""s knowledge is encoded to form a knowledge base, or a repository of information needed to solve a problem. A knowledge representation fact base can be thought of as comprising a number of related components called knowledge objects, where each object exists in a specific relationship to other objects in the knowledge representation fact base. Objects in a knowledge representation fact base represent the different components into which actual facts in the real world can be remembered and used. The specific terminology and definitions used in a given knowledge representation fact base are referred to as the knowledge representation paradigm""s ontology: the terms knowledge representation fact base and ontology are often used interchangeably.
A reasoning system is the logic underlying a decision support system. A reasoning system of a decision support system is the logic component of the decision support system, as opposed to the knowledge repository component. A reasoning system is the mechanism that uses a knowledge representation model to make inferences about objects in the knowledge representation fact base. During a decision support session, a knowledge representation paradigm is employed to find a solution to a problem. A reasoning system of the knowledge representation paradigm invokes an algorithm using its knowledge representation model to operate on knowledge in the system""s knowledge representation fact base. A knowledge representation model can be a tree, or a graph, for example. Oftentimes, the terms knowledge representation paradigm and reasoning system are used synonymously. In large part, this is because in current systems, a knowledge representation fact base is inseparably part of a corresponding reasoning system: a knowledge representation fact base has semantics that are usually closely tied to a reasoning system algorithm.
Examples of existing knowledge representation paradigms include basic text, decision trees, decision graphs, case-bases, default logic, augmented fault, and Bayesian belief networks. In a decision tree knowledge representation paradigm, for example, the knowledge representation fact base is composed of a number of question and answer knowledge objects, wherein knowledge is encoded into a knowledge base in the form of question and answer tests. The reasoning system of the decision tree knowledge representation paradigm comprises an algorithm of IF-THEN-ELSE statements that operate on the knowledge objects to create a tree model. The tree model encapsulates a series of decision flows that can be made using the question and answer objects in a decision support session. The logic of the IF-THEN-ELSE statements then dictate the relationship between these objects. Just as there are many different programming languages, each best suited for certain types of projects (e.g., FORTRAN for number crunching, Visual Basic for GUI development, C++ for object-oriented solutions), there are also many different ways for representing knowledge, some more appropriate for a given problem domain (i.e. subject matter) than others.
One example of a currently available decision support system is Hewlett-Packard""s internal KnowledgeTrees system used for customer support. In KnowledgeTrees, decision graphs are explicitly coded with answers to the questions which lead to a solution. A decision support system such as KnowledgeTrees has several drawbacks. First, since each question can only have one of multiple hard-coded answers, multiple conclusions are not supported. Secondly, this system is not designed to allow the same question-answer to be explored for a given problem. For example, the same question-answer cannot be explored multiple times for each printer in a network. Furthermore, while decision graphs are useful for small and moderately complex graphs, and are typically easy to author, the cost of maintaining consistency and authoring against large and complex graphs is prohibitive. Also, decision graphs are insufficient to encode the problems of complex inter-dependent system problems, particularly when distributed automated agents are needed.
KnowledgePak, a diagnostic support system sold by ServiceWare, is similar to KnowledgeTrees in that it integrates the questions and answers with the control logic. KnowledgePak, however, uses a case-based structure, using a case as the defining and organizing object. Other objects in KnowledgePak include Symptoms, CaseDetail, and Solution Definition Objects. KnowledgePak is limited to isolating a diagnostic problem to a single case or conclusion. Authoring into KnowledgePak requires significant expertise with the tool and with the diagnostic domain as authors are required to be able to distinguish among object types such as cases, causes, tests, remedies, and various other objects in KnowledgePak.
AdvantageKBS from Logica Corporation is based on an augmented fault model. This fault model is based on symptom, cause, test, and solution object classes. Each class describes a part of the diagnostic system requiring distinct relationships between objects in the class and to objects of other classes. Again, the goal of the decision support model is to isolate a single case that applies to the current session. The vendors of this knowledge base discourage wide authorship since the creation of usable diagnostic knowledge into their fault model requires special training.
E-Diagnostic, the current generation of self-solve diagnostic systems from Hewlett-Packard Company, is representative of classic diagnostic support systems. It is implemented by creating custom code that encodes the reasoning, knowledge, data collection and conclusions within a single program. The barrier to authorship is unacceptably high. Each author not only requires adequate domain knowledge of the diagnostic he or she is authoring, but also requires knowledge of software design and C++ programming (the language in which the program is written). The author then needs to integrate his module into the main product. The specialized skills required of authors for such decision support systems does not allow fast and flexible creation or modification to the systems.
This invention addresses some of the deficiencies of currently available reasoning systems of knowledge representation paradigms. Reasoning systems of existing paradigms tend to associate problems with a single cause, or origin of the problem. This limits the wide range of decisions that can potentially be made with respect to a given problem, and limits the conclusions that can be inferred from the decisions. Furthermore, these reasoning systems do not support reentrant capabilities, or the ability for a given part of a defining knowledge structure to be repeatedly explored, such as in different contexts. Lastly, these reasoning systems have not struck the critical balance between the simplicity of a knowledge representation that encourages wide authorship by experts, and the depth of representation necessary to make the knowledge usable by a knowledge reasoning system.
A need exists for a method and apparatus to address these concerns.
This invention is, in general, directed to a method and apparatus for a compositional decision support reasoning system.
Thus, the invention may comprise apparatus for determining one or more solutions to a problem, comprising at least one computer readable medium and computer readable program code stored on the computer readable medium, comprising program code for traversing at least one path in one of at least one pursuit associated with the problem to generate one or more decision paths, the code comprising program code for processing a given one of the nodes in a path, comprising program code for evaluating a premise if the node type is a premise node, and passing the premise node if said premise passes, and program code for noting a conclusion if the node type is a conclusion node, for withdrawing any previous conclusions that are not associated with a parent node of the conclusion, and passing the conclusion node; program code for processing a child node of the current node if the current node is not a leaf node and is a node that passes; program code for terminating one of the decision paths if the child node cannot be processed, comprising asserting all noted, but non-withdrawn conclusions; and program code for generating a second of one or more paths in a given pursuit.
The invention may also comprise an apparatus for determining one or more solutions to a problem, comprising means for processing a given one of at least one node, the processing comprising means for evaluating a premise if the node type is a premise node, and passing the premise node if the premise passes; and means for noting a conclusion if the node type is a conclusion node, for withdrawing any previous conclusions that are not associated with a parent node of the conclusion, and passing said conclusion node; means for processing a child node of the current node if the current node is not a leaf node and is a node that passes; means for terminating a decision path if the child node cannot be processed, comprising asserting all noted, but non-withdrawn conclusions; and means for generating a second of one or more decision paths.
The invention may further comprise a method for determining one or more solutions to a problem, comprising traversing at least one path in one of at least one pursuit to generate one or more decision paths, the traversing comprising processing a given one of the nodes in a path, the processing comprising evaluating a premise if the node type is a premise node, and passing the premise node if the premise passes; and noting a conclusion if the node type is a conclusion node, withdrawing any previous conclusions that are not associated with a parent node of the conclusion, and passing the conclusion node; processing a child node of the current node if the current node is not a leaf node and is a node that passes; terminating a decision path if the child node cannot be processed, comprising asserting all noted, but non-withdrawn conclusions as a solution to the problem; and generating a second of said one or more decision paths.